package 中等.贪心思想;

/**
 * 给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：
 * 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -1 。
 * 如果两个元素有 公共边 ，那么它们就是 相邻 的。
 * 你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-matrix-sum
 */
public class 最大方阵和_1975 {

    public static void main(String[] args) {

        int[][] matrix = {{1, -1}, {-1, 1}};
        System.out.println(maxMatrixSum(matrix));

    }

    /**
     * 1，对于方阵中的两个 负数 ，一定可以通过移动，来使得两个 负数
     * 变成 正数，从而使得整体变大
     * 2，那么当 负数个数 为偶数时，一定可以使得方阵中的数字全部变成
     * 正数，
     * 3，特别的，如果方阵中存在 0 ，负数个数为奇数个时，剩下的那个
     * 负数可以和 0 ，交换符号，从而使得所有数为 >=0 的数
     * 4，当方阵中不存在 0，且负数个数为奇数时，负号可以通过移动放
     * 到任意一个数字的位置，那么优先选择，较小的数字，从而使得整体
     * 更大
     *
     * @param matrix
     * @return
     */
    public static long maxMatrixSum(int[][] matrix) {
        int count = 0, min = Math.abs(matrix[0][0]);
        long sumAbs = 0;
        boolean hasZero = false;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] < 0) count++;
                if (matrix[i][j] == 0) hasZero = true;
                min = Math.min(min, Math.abs(matrix[i][j]));
                sumAbs += Math.abs(matrix[i][j]);
            }
        }
        // sumAbs 是加上了最小的那个数的和，所以需要 min*2
        return (hasZero || count % 2 == 0) ? sumAbs : sumAbs - 2 * Math.abs(min);
    }

}
